package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/?envType=study-plan-v2&envId=top-interview-150/">二叉搜索树的最小绝对差(Minimum Absolute Difference in BST)</a>
 * <p>给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。</p>
 * <p>差值是一个正数，其数值等于两值之差的绝对值。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [4,2,6,1,3]
 *      输出：1
 *
 * 示例 2：
 *      输入：root = [1,0,48,null,null,12,49]
 *      输出：1
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目范围是 [2, 10^4]</li>
 *     <li>0 <= Node.val <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/18 18:56
 */
public class _LC0530MinimumAbsoluteDifferenceInBST_S {

    static class Solution {
        int minimumDifference = Integer.MAX_VALUE;
        int preNodeVal = -1;

        public int getMinimumDifference(TreeNode root) {
            dfs(root);
            return minimumDifference;
        }

        private void dfs(TreeNode node) {
            if (node == null) {
                return;
            }
            dfs(node.left);
            if (preNodeVal == -1) {
                preNodeVal = node.val;
            } else {
                minimumDifference = Math.min(minimumDifference, node.val - preNodeVal);
            }
            dfs(node.right);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(0);
        root1.right = new TreeNode(48);
        root1.right.left = new TreeNode(12);
        root1.right.right = new TreeNode(49);
        System.out.println(solution.getMinimumDifference(root1));

        TreeNode root2 = new TreeNode(4);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(6);
        root2.left.left = new TreeNode(1);
        root2.left.right = new TreeNode(3);
        System.out.println(solution.getMinimumDifference(root2));

        TreeNode root3 = new TreeNode(1);
        root3.right = new TreeNode(3);
        root3.right.left = new TreeNode(2);
        System.out.println(solution.getMinimumDifference(root3));
    }
}
